1. Field of the Invention
The present invention relates to verification of logic designs. More specifically, the present invention relates to formal property verification of logic designs using abstraction refinement.
2. Related Art
Formal property verification exhaustively verifies logic designs against desired properties of the designs with respect to all possible input sequences of any length. An important application of formal verification is to prove safety properties for logic designs. Informally, proving a safety property guarantees that certain “bad” states are not reachable from the initial states through any traces of the design. A counter example of a safety property is a trace that reaches a bad state from an initial state of the design.
Brute force approaches to prove safety properties of logic designs are usually not practical. For example, approaches based on Binary Decision Diagrams (BDD) or clauses in Boolean satisfiability solvers usually cannot verify properties of designs with more than a couple of hundred registers. As a result, formal property verification techniques typically rely on automatic abstraction techniques to verify real-world logic designs.
Abstraction refinement is a popular automatic abstraction method. Abstraction refinement incrementally refines the abstract model, a subset of the design, by including more and more logic from the original design until the underlying formal property verification engine verifies or falsifies the property.
Since the performance of an underlying formal property verification engine decreases as the complexity of the abstract model increases, the biggest challenge of an abstraction refinement algorithm is to buildup an abstract model that is as simple as possible but contains enough details to verify the property.
Unfortunately, prior art techniques for abstraction refinement build abstraction models that are more complex than what is required to prove the safety property, which reduces the performance of the overall verification process.
Hence, what is needed is a method and an apparatus for abstraction refinement that does not build overly complex abstract models.